class Solution {
    /**
     * 方法一
     * @param matrix
     * @return
     */
    public int maximalSquare1(char[][] matrix) {
        int width = matrix.length;
        int height = 0;
        if (width > 0) {
            height = matrix[0].length;
        } else {
            height = 0;
        }

        int bianchang = 0;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (matrix[i][j] == '1') {
                    int L = 1;
                    int H = 1;
                    boolean isMeet = true;
                    while (L + i < width && H + j < height && isMeet) {
                        for (int a = i; a <= L + i; a++) {
                            if (matrix[a][H + j] == '0') {
                                isMeet = false;
                                break;
                            }
                        }

                        for (int b = j; b <= H + j; b++) {
                            if (matrix[L + i][b] == '0') {
                                isMeet = false;
                                break;
                            }
                        }
                        if (isMeet) {
                            L = L + 1;
                            H = H + 1;
                        }
                    }
                    if (bianchang < L) {
                        bianchang = L;
                    }
                }
            }
        }
        return bianchang * bianchang;

    }

    /**
     * 方法二
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int db[][] = new int[matrix.length][matrix[0].length];
        int maxLong = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 || j == 0) {
                    if (matrix[i][j] == '0') {
                        db[i][j] = 0;
                    } else {
                        db[i][j] = 1;
                        if (maxLong < 1) {
                            maxLong = 1;
                        }
                    }
                } else {
                    if (matrix[i][j] == '0') {
                        db[i][j] = 0;
                    } else {
                        db[i][j] = Math.min(db[i - 1][j], Math.min(db[i - 1][j - 1], db[i][j - 1])) + 1;
                        if (maxLong < db[i][j]) {
                            maxLong = db[i][j];
                        }
                    }
                }
            }
        }
        return maxLong * maxLong;
    }
}